<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0"><meta name="theme-color" content="#0078E7"><meta name="author" content="Shinya"><meta name="copyright" content="Shinya"><meta name="generator" content="Hexo 5.4.0"><meta name="theme" content="hexo-theme-yun"><title>洗牌算法 | 夤夜的世界旅行手记</title><link rel="stylesheet" href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@900&amp;display=swap" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/star-markdown-css@0.1.24/dist/yun/yun-markdown.min.css"><script src="//at.alicdn.com/t/font_1140697_j5gk85dg4pf.js" async></script><script src="https://cdn.jsdelivr.net/npm/scrollreveal/dist/scrollreveal.min.js" defer></script><script>document.addEventListener("DOMContentLoaded", () => {
  [".post-card",".post-content img"].forEach((target)=> {
    ScrollReveal().reveal(target);
  })
});
</script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/katex@latest/dist/katex.min.css"><script defer src="https://cdn.jsdelivr.net/npm/katex@latest/dist/katex.min.js"></script><link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/npm/katex@latest/dist/contrib/copy-tex.min.css"><script defer src="https://cdn.jsdelivr.net/npm/katex@latest/dist/contrib/copy-tex.min.js"></script><script defer src="https://cdn.jsdelivr.net/npm/katex@latest/dist/contrib/auto-render.min.js"></script><script>document.addEventListener("DOMContentLoaded", () => {
  Yun.utils.renderKatex();
});</script><link id="light-prism-css" rel="stylesheet" href="https://cdn.jsdelivr.net/npm/prismjs@latest/themes/prism.css" media="(prefers-color-scheme: light)"><link id="dark-prism-css" rel="stylesheet" href="https://cdn.jsdelivr.net/npm/prismjs@latest/themes/prism-tomorrow.css" media="(prefers-color-scheme: dark)"><link rel="icon" href="https://upimage.alexhchu.com/2021/04/19/abe22a9e40f16.jpg"><link rel="mask-icon" href="https://upimage.alexhchu.com/2021/04/19/abe22a9e40f16.jpg" color="#0078E7"><link rel="alternate icon" href="/yun.ico"><link rel="preload" href="/css/hexo-theme-yun.css" as="style"><link rel="preload" href="/js/utils.js" as="script"><link rel="preload" href="/js/hexo-theme-yun.js" as="script"><link rel="prefetch" href="/js/sidebar.js" as="script"><link rel="preconnect" href="https://cdn.jsdelivr.net" crossorigin><script id="yun-config">
    const Yun = window.Yun || {};
    window.CONFIG = {"hostname":"shinya754.gitee.io","root":"/","title":"夤夜的世界旅行手记","version":"1.6.1","mode":"time","copycode":true,"page":{"isPost":true},"i18n":{"placeholder":"搜索...","empty":"找不到您查询的内容: ${query}","hits":"找到 ${hits} 条结果","hits_time":"找到 ${hits} 条结果（用时 ${time} 毫秒）"},"anonymous_image":"https://cdn.jsdelivr.net/gh/YunYouJun/cdn/img/avatar/none.jpg","say":{"api":"https://v1.hitokoto.cn","hitokoto":true},"fireworks":{"colors":["153, 153, 255","255, 255, 0","51, 255, 0"]}};
  </script><link rel="stylesheet" href="/css/hexo-theme-yun.css"><script src="/js/utils.js"></script><script src="/js/hexo-theme-yun.js"></script><meta name="description" content="突然发现我的知识盲区好像有点大这里记录三种常用的洗牌算法。">
<meta property="og:type" content="article">
<meta property="og:title" content="洗牌算法">
<meta property="og:url" content="https://shinya754.gitee.io/2021/05/13/%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95/index.html">
<meta property="og:site_name" content="夤夜的世界旅行手记">
<meta property="og:description" content="突然发现我的知识盲区好像有点大这里记录三种常用的洗牌算法。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://upimage.alexhchu.com/2021/05/14/7c5af6a62cff8.png">
<meta property="og:image" content="https://upimage.alexhchu.com/2021/05/14/66eb2113cf548.png">
<meta property="og:image" content="https://upimage.alexhchu.com/2021/05/14/15a1b33345511.png">
<meta property="article:published_time" content="2021-05-13T14:29:45.000Z">
<meta property="article:modified_time" content="2021-05-15T01:30:04.682Z">
<meta property="article:author" content="Shinya">
<meta property="article:tag" content="学习">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://upimage.alexhchu.com/2021/05/14/7c5af6a62cff8.png"><script src="/js/ui/mode.js"></script></head><body><script defer src="https://cdn.jsdelivr.net/npm/animejs@latest"></script><script defer src="/js/ui/fireworks.js"></script><canvas class="fireworks"></canvas><div class="container"><a class="sidebar-toggle hty-icon-button" id="menu-btn"><div class="hamburger hamburger--spin" type="button"><span class="hamburger-box"><span class="hamburger-inner"></span></span></div></a><div class="sidebar-toggle sidebar-overlay"></div><aside class="sidebar"><script src="/js/sidebar.js"></script><ul class="sidebar-nav"><li class="sidebar-nav-item sidebar-nav-toc hty-icon-button sidebar-nav-active" data-target="post-toc-wrap" title="文章目录"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-list-ordered"></use></svg></li><li class="sidebar-nav-item sidebar-nav-overview hty-icon-button" data-target="site-overview-wrap" title="站点概览"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-passport-line"></use></svg></li></ul><div class="sidebar-panel" id="site-overview-wrap"><div class="site-info fix-top"><a class="site-author-avatar" href="/about/" title="Shinya"><img width="96" loading="lazy" src="https://upimage.alexhchu.com/2021/04/19/abe22a9e40f16.jpg" alt="Shinya"><span class="site-author-status" title="You'll see this world is wonderful.">😊</span></a><div class="site-author-name"><a href="/about/">Shinya</a></div><span class="site-name">夤夜的世界旅行手记</span><sub class="site-subtitle">你好，陌生人。</sub><div class="site-desciption">某211软工专业在读</div></div><nav class="site-state"><a class="site-state-item hty-icon-button icon-home" href="/" title="首页"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-home-4-line"></use></svg></span></a><div class="site-state-item"><a href="/archives/" title="归档"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-archive-line"></use></svg></span><span class="site-state-item-count">23</span></a></div><div class="site-state-item"><a href="/categories/" title="分类"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-2-line"></use></svg></span><span class="site-state-item-count">4</span></a></div><div class="site-state-item"><a href="/tags/" title="标签"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="site-state-item-count">12</span></a></div><a class="site-state-item hty-icon-button" target="_blank" rel="noopener" href="http://121.4.147.128:8888/profile?id=%E5%A4%8F%E8%89%B2%E5%8D%83%E7%BB%AB" title="TOS战绩"><span class="site-state-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-open-arm-line"></use></svg></span></a></nav><hr style="margin-bottom:0.5rem"><div class="links-of-author"><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://github.com/Shinya754" title="GitHub" target="_blank" style="color:#6e5494"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-github-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://music.163.com/#/user/home?id=114080703" title="网易云音乐" target="_blank" style="color:#C20C0C"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-netease-cloud-music-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://www.zhihu.com/people/yin-ye-14-16" title="知乎" target="_blank" style="color:#0084FF"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-zhihu-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://space.bilibili.com/4950796" title="哔哩哔哩" target="_blank" style="color:#FF8EB3"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-bilibili-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="https://twitter.com/Shinya433" title="Twitter" target="_blank" style="color:#1da1f2"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-twitter-line"></use></svg></a><a class="links-of-author-item hty-icon-button" rel="noopener" href="mailto:shinya754@qq.com" title="E-Mail" target="_blank" style="color:#8E71C1"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-mail-line"></use></svg></a></div><hr style="margin:0.5rem 1rem"><div class="links"><a class="links-item hty-icon-button" href="/links/" title="我的小伙伴们" style="color:dodgerblue"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-genderless-line"></use></svg></a></div><br><a class="links-item hty-icon-button" id="toggle-mode-btn" href="javascript:;" title="Mode" style="color: #f1cb64"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-contrast-2-line"></use></svg></a></div><div class="sidebar-panel sidebar-panel-active" id="post-toc-wrap"><div class="post-toc"><div class="post-toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#Fisher-Yates%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95"><span class="toc-number">1.</span> <span class="toc-text">Fisher-Yates洗牌算法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Knuth-Durstenfeld%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95"><span class="toc-number">2.</span> <span class="toc-text">Knuth-Durstenfeld洗牌算法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Inside-Out%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95"><span class="toc-number">3.</span> <span class="toc-text">Inside-Out洗牌算法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%8D%E7%9F%A5%E9%81%93%E5%90%8D%E5%AD%97%E7%9A%84%E7%AE%97%E6%B3%95"><span class="toc-number">4.</span> <span class="toc-text">不知道名字的算法</span></a></li></ol></div></div></div></aside><main class="sidebar-translate" id="content"><div id="post"><article class="hty-card post-block" itemscope itemtype="https://schema.org/Article"><link itemprop="mainEntityOfPage" href="https://shinya754.gitee.io/2021/05/13/%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95/"><span hidden itemprop="author" itemscope itemtype="https://schema.org/Person"><meta itemprop="name" content="Shinya"><meta itemprop="description"></span><span hidden itemprop="publisher" itemscope itemtype="https://schema.org/Organization"><meta itemprop="name" content="夤夜的世界旅行手记"></span><header class="post-header"><h1 class="post-title" itemprop="name headline">洗牌算法</h1><div class="post-meta"><div class="post-time" style="display:inline-block"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-line"></use></svg></span> <time title="创建时间：2021-05-13 22:29:45" itemprop="dateCreated datePublished" datetime="2021-05-13T22:29:45+08:00">2021-05-13</time><span class="post-meta-divider">-</span><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-calendar-2-line"></use></svg></span> <time title="修改时间：2021-05-15 09:30:04" itemprop="dateModified" datetime="2021-05-15T09:30:04+08:00">2021-05-15</time></div><div class="post-classify"><span class="post-category"> <span class="post-meta-item-icon" style="margin-right:3px;"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-folder-line"></use></svg></span><span itemprop="about" itemscope itemtype="https://schema.org/Thing"><a class="category-item" href="/categories/%E7%AE%97%E6%B3%95/" style="--text-color:var(--hty-text-color)" itemprop="url" rel="index"><span itemprop="text">算法</span></a></span></span><span class="post-tag"><span class="post-meta-divider">-</span><a class="tag-item" href="/tags/%E5%AD%A6%E4%B9%A0/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">学习</span></a><a class="tag-item" href="/tags/%E7%AE%97%E6%B3%95/" style="--text-color:var(--hty-text-color)"><span class="post-meta-item-icon"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-price-tag-3-line"></use></svg></span><span class="tag-name">算法</span></a></span></div></div></header><section class="post-body" itemprop="articleBody"><div class="post-content markdown-body" style="--smc-primary:#0078E7;"><p>突然发现我的知识盲区好像有点大<br>这里记录三种常用的洗牌算法。</p>
<span id="more"></span>

<h2 id="Fisher-Yates洗牌算法"><a href="#Fisher-Yates洗牌算法" class="headerlink" title="Fisher-Yates洗牌算法"></a>Fisher-Yates洗牌算法</h2><p>&emsp;核心思想是创建一个新数组，每次从原数组中选一个之前没有选过的元素加入到新数组的末尾。<br>&emsp;一眼就能看懂的东西就直接上代码了：（C#）</p>
<pre class="language-csharp" data-language="csharp"><code class="language-csharp"><span class="token keyword">public</span> <span class="token return-type class-name">List<span class="token punctuation">&lt;</span><span class="token keyword">int</span><span class="token punctuation">></span></span> <span class="token function">Fisher_Yates_Shuffle</span><span class="token punctuation">(</span><span class="token class-name">List<span class="token punctuation">&lt;</span><span class="token keyword">int</span><span class="token punctuation">></span></span> originList<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token class-name">List<span class="token punctuation">&lt;</span><span class="token keyword">int</span><span class="token punctuation">></span></span> returnList <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token constructor-invocation class-name">List<span class="token punctuation">&lt;</span><span class="token keyword">int</span><span class="token punctuation">></span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//创建一个新数组用于存储打乱后的数据</span>
    <span class="token class-name"><span class="token keyword">var</span></span> rand <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token constructor-invocation class-name">Random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//通过Random类的实例获取随机数</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>originList<span class="token punctuation">.</span>Count <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token class-name"><span class="token keyword">int</span></span> randNum <span class="token operator">=</span> rand<span class="token punctuation">.</span><span class="token function">Next</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> originList<span class="token punctuation">.</span>Count<span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment">//Random.Next()方法,在左闭右开区间内生成随机整数。</span>
        <span class="token class-name"><span class="token keyword">int</span></span> numToAdd <span class="token operator">=</span> originList<span class="token punctuation">[</span>randNum<span class="token punctuation">]</span><span class="token punctuation">;</span>
        originList<span class="token punctuation">.</span><span class="token function">RemoveAt</span><span class="token punctuation">(</span>randNum<span class="token punctuation">)</span><span class="token punctuation">;</span>
        returnList<span class="token punctuation">.</span><span class="token function">Add</span><span class="token punctuation">(</span>numToAdd<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> returnList<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>代码也是一眼就能看懂。<br>&emsp;由于使用数组（List底层是数组）实现，所以总体时间复杂度是O(n<sup>2</sup>)，而由于使用了一个最大长度与原来数组相等的数组，所以空间复杂度是O(n)。</p>
<p>&emsp;对原数组中每一个元素都能等概率地出现在新数组中每一个位置的证明：<br>&emsp;元素m被放置在i位置的概率，即为元素m没有被放置在前i-1个位置的概率乘以放置元素在第i个位置时选中元素m的概率。<br>&emsp;元素m不被放置在第一个位置的概率为 $\frac{n-1}{n}$（最初共有<code>n</code>个元素，除了元素m之外还有<code>n-1</code>个元素。），不被放置在第2个位置的概率为$\frac{n-2}{n-1}$，以此类推，不被放置在第i-1个位置的概率为$\frac{n-(i-1)}{n-(i-1)+1}$，被放置在第i个位置的概率为$\frac{1}{n-(i-1)}$（选中元素m前已经选走了<code>i-1</code>个元素，还剩<code>n-(i-1)</code>个元素），将这些概率相乘则得到元素m被放置在位置i的概率为$\frac{1}{n}$。<br>&emsp;手写笔记：（字比较丑，图一乐）<br><img src="https://upimage.alexhchu.com/2021/05/14/7c5af6a62cff8.png" alt="笔记FisherYates" loading="lazy"></p>
<h2 id="Knuth-Durstenfeld洗牌算法"><a href="#Knuth-Durstenfeld洗牌算法" class="headerlink" title="Knuth-Durstenfeld洗牌算法"></a>Knuth-Durstenfeld洗牌算法</h2><p>&emsp;Fisher-Yates算法使用了额外空间来存储打乱后的数组，导致算法的空间复杂度为O(n)，而Knuth-Durstenfeld算法原地修改输入数组，将空间复杂度降低到了O(1)。<br>&emsp;核心思想是将数组划分为有序区和打乱区两个部分（为了描述方便，我们暂且认为打乱前的数组是有序的），有序区在打乱区的前面。在数组被打乱之前，整个数组都是有序区。每次，在有序区中随机选择一个元素，将其与有序区的末尾元素交换，直到整个数组都是打乱区。<br>&emsp;代码如下：（C#）</p>
<pre class="language-csharp" data-language="csharp"><code class="language-csharp"><span class="token keyword">public</span> <span class="token return-type class-name"><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span></span> <span class="token function">Knuth_Durstenfeld_Shuffle</span><span class="token punctuation">(</span><span class="token class-name"><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span></span> originNums<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token class-name"><span class="token keyword">var</span></span> rand <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token constructor-invocation class-name">Random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token class-name"><span class="token keyword">int</span></span> i <span class="token operator">=</span> originNums<span class="token punctuation">.</span>Length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token class-name"><span class="token keyword">int</span></span> randNum <span class="token operator">=</span> rand<span class="token punctuation">.</span><span class="token function">Next</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token comment">//交换这两个数</span>
        <span class="token class-name"><span class="token keyword">int</span></span> temp <span class="token operator">=</span> originNums<span class="token punctuation">[</span>randNum<span class="token punctuation">]</span><span class="token punctuation">;</span>
        originNums<span class="token punctuation">[</span>randNum<span class="token punctuation">]</span> <span class="token operator">=</span> originNums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
        originNums<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> originNums<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>&emsp;我最初实现这个算法的时候犯蠢了，因为最近力扣搁那整异或周，导致我在交换两个数的时候用了<code>a^=b;b^=a;a^=b</code>的方法，但是这里<code>randNum</code>是可以等于i的（否则原来的最后一个数必定不在最后），结果就成了<code>a^=a;a^=a;a^=a</code>，然后结果就变成了0。<br>&emsp;这个算法除了改进了Fisher-Yates算法的空间复杂度，还顺便把时间复杂度也给改进了，因为这个算法中不再进行数组的插入和删除。时间复杂度为O(n)。</p>
<p>&emsp;对原数组中每一个元素都能等概率地出现在新数组中每一个位置的证明：<br>&emsp;先上图方便说明，假设数组长度为<code>n</code>：<br><img src="https://upimage.alexhchu.com/2021/05/14/66eb2113cf548.png" alt="笔记KnuthDurstenfeld" loading="lazy"><br>&emsp;首先对于元素<code>4</code>，出现在每一个位置的概率都是$\frac{1}{n}$，这很容易理解；<br>&emsp;然后对于元素<code>3</code>，出现在位置4（即数组末尾的那个位置）的概率即为元素<code>4</code>选中元素<code>3</code>的概率$\frac{1}{n}$，而出现在位置3以及之前的概率为元素<code>4</code>没有选中元素<code>3</code>的概率乘以$\frac{n-2}{n-1}$（元素3以及之前元素的长度为<code>n-1</code>），也是$\frac{1}{n}$；<br>&emsp;然后对于元素<code>2</code>，出现在位置4的概率为$\frac{1}{n}$，出现在位置3的概率为元素<code>4</code>没有选到元素<code>2</code>的概率乘以元素<code>3</code>选到元素<code>2</code>的概率，即$\frac{n-1}{n}$*$\frac{1}{n-1}$=$\frac{1}{n}$，出现在位置2以及之前的概率同样为$\frac{1}{n}$，其他元素以此类推。实际上虽然实现略有不同，但是证明思路以及写出来的计算式和Fisher-Yates算法是完全一致的。（毕竟是它的改进版本）</p>
<h2 id="Inside-Out洗牌算法"><a href="#Inside-Out洗牌算法" class="headerlink" title="Inside-Out洗牌算法"></a>Inside-Out洗牌算法</h2><p>&emsp;前两种洗牌算法都有一个共性，就是会改变输入的数组（当然Knuth-Durstenfeld算法可以在方法内复制一个数组从而避免对数组数组的修改，但是人家核心思想就是原地修改…），在有些情况下，我们需要保留输入的数组，使用Inside-Out洗牌算法可以解决这个问题。<br>&emsp;核心思想是先创建一个原数组的复制（毕竟要保留原数组），然后使用类似Knuth-Durstenfeld算法的思路，将数组的前面部分视为打乱区，后面没有处理过的部分视为有序区，每次将有序区的第一个元素与打乱区的随机一个元素交换，然后打乱区大小+1，实现上其实就是Knuth-Durstenfeld算法的反向版本，但是由于Inside-Out算法从前往后扫描数组，所以如果数组以数据流的形式传入，或者无法读取数组长度时，只能使用这种算法，而前两种算法无法使用。<br>&emsp;代码如下：(C#)</p>
<pre class="language-csharp" data-language="csharp"><code class="language-csharp"><span class="token keyword">public</span> <span class="token return-type class-name"><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span></span> <span class="token function">Inside_Out_Shuffle</span><span class="token punctuation">(</span><span class="token class-name"><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span></span> originNums<span class="token punctuation">)</span>
<span class="token punctuation">&#123;</span>
    <span class="token class-name"><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span></span> resultArr <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token constructor-invocation class-name"><span class="token keyword">int</span></span><span class="token punctuation">[</span>originNums<span class="token punctuation">.</span>Length<span class="token punctuation">]</span><span class="token punctuation">;</span>
    Array<span class="token punctuation">.</span><span class="token function">Copy</span><span class="token punctuation">(</span>originNums<span class="token punctuation">,</span> resultArr<span class="token punctuation">,</span> originNums<span class="token punctuation">.</span>Length<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token class-name"><span class="token keyword">var</span></span> rand <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token constructor-invocation class-name">Random</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token class-name"><span class="token keyword">int</span></span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> originNums<span class="token punctuation">.</span>Length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
    <span class="token punctuation">&#123;</span>
        <span class="token class-name"><span class="token keyword">int</span></span> randNum <span class="token operator">=</span> rand<span class="token punctuation">.</span><span class="token function">Next</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        resultArr<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> resultArr<span class="token punctuation">[</span>randNum<span class="token punctuation">]</span><span class="token punctuation">;</span>
        resultArr<span class="token punctuation">[</span>randNum<span class="token punctuation">]</span> <span class="token operator">=</span> originNums<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment">//扩展打乱区后，将刚加入打乱区的数和打乱区内的随机一个数交换。</span>
        <span class="token comment">//借用原数组i位置的元素就不需要使用临时变量来处理数字交换了（</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> resultArr<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>&emsp;时间复杂度为O(n)，空间复杂度为O(n)。<br>&emsp;证明和Knuth-Durstenfeld算法完全一致。<br>&emsp;笔记图一乐。<br><img src="https://upimage.alexhchu.com/2021/05/14/15a1b33345511.png" alt="笔记Inside-Out" loading="lazy"></p>
<h2 id="不知道名字的算法"><a href="#不知道名字的算法" class="headerlink" title="不知道名字的算法"></a>不知道名字的算法</h2><p>&emsp;当年写俄罗斯方块7Bag的时候在网上学了这个算法：</p>
<pre class="language-csharp" data-language="csharp"><code class="language-csharp"><span class="token keyword">private</span> <span class="token return-type class-name">List<span class="token punctuation">&lt;</span>T<span class="token punctuation">></span></span> <span class="token generic-method"><span class="token function">RandomSort</span><span class="token generic class-name"><span class="token punctuation">&lt;</span>T<span class="token punctuation">></span></span></span><span class="token punctuation">(</span><span class="token class-name">List<span class="token punctuation">&lt;</span>T<span class="token punctuation">></span></span> list<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span><span class="token comment">//这会返回一个顺序被打乱的List且不改变传入的list</span>
    <span class="token class-name"><span class="token keyword">var</span></span> newList <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token constructor-invocation class-name">List<span class="token punctuation">&lt;</span>T<span class="token punctuation">></span></span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token keyword">foreach</span> <span class="token punctuation">(</span><span class="token class-name"><span class="token keyword">var</span></span> item <span class="token keyword">in</span> list<span class="token punctuation">)</span> <span class="token punctuation">&#123;</span>
        newList<span class="token punctuation">.</span><span class="token function">Insert</span><span class="token punctuation">(</span>Random<span class="token punctuation">.</span><span class="token function">Range</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span>newList<span class="token punctuation">.</span>Count<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span> item<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">&#125;</span>
    <span class="token keyword">return</span> newList<span class="token punctuation">;</span>
<span class="token punctuation">&#125;</span></code></pre>
<p>&emsp;代码非常简洁，而且思路也很简单，就是对原数组中的每一个元素，依次将其随机插入新数组中，就像是从牌堆里按顺序抓牌，但是随机地插入手上的牌中。<br>&emsp;由于出现了数组的插入，时间复杂度是O($n^2$)，使用了额外空间以保证不改动原数组，空间复杂度为O(n)。<br>&emsp;证明似乎相当麻烦，不过我们可以很简单地证明原位置为0和n-1的元素出现在位置0和n-1的概率都是$\frac{1}{n}$。<br>&emsp;不过我猜这个算法应该也是满足每一个元素出现在每一个位置的概率相等的。</p>
<p>思路参考：<a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_26399665/article/details/79831490">https://blog.csdn.net/qq_26399665/article/details/79831490</a></p>
</div><div id="reward-container"><span class="hty-icon-button button-glow" id="reward-button" title="打赏" onclick="var qr = document.getElementById(&quot;qr&quot;); qr.style.display = (qr.style.display === &quot;none&quot;) ? &quot;block&quot; : &quot;none&quot;;"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-hand-coin-line"></use></svg></span><div id="reward-comment">希望我提供的帮助能够补偿你在这里花费的时间。</div><div id="qr" style="display:none;"><div style="display:inline-block"></div></div></div><ul class="post-copyright"><li class="post-copyright-author"><strong>本文作者：</strong>Shinya</li><li class="post-copyright-link"><strong>本文链接：</strong><a href="https://shinya754.gitee.io/2021/05/13/%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95/" title="洗牌算法">https://shinya754.gitee.io/2021/05/13/%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95/</a></li><li class="post-copyright-license"><strong>版权声明：</strong>本博客所有文章除特别声明外，均默认采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" target="_blank" rel="noopener" title="CC BY-NC-SA 4.0 "><svg class="icon"><use xlink:href="#icon-creative-commons-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-by-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-nc-line"></use></svg><svg class="icon"><use xlink:href="#icon-creative-commons-sa-line"></use></svg></a> 许可协议。</li></ul></section></article><div class="post-nav"><div class="post-nav-item"><a class="post-nav-prev" href="/2021/05/16/%E5%8A%9B%E6%89%A3421-%E6%95%B0%E7%BB%84%E4%B8%AD%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%9A%84%E6%9C%80%E5%A4%A7%E5%BC%82%E6%88%96%E5%80%BC/" rel="prev" title="力扣421.数组中两个数的最大异或值"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-left-s-line"></use></svg><span class="post-nav-text">力扣421.数组中两个数的最大异或值</span></a></div><div class="post-nav-item"><a class="post-nav-next" href="/2021/05/07/%E8%8B%B1-%E6%B1%89-%E8%AF%8D-%E5%85%B8%EF%BC%88%E8%BF%AB%E7%9C%9F/" rel="next" title="英 汉 词 典（迫真"><span class="post-nav-text">英 汉 词 典（迫真</span><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-right-s-line"></use></svg></a></div></div></div><div class="hty-card" id="comment"><div class="comment-tooltip text-center"><span>这里是大图书馆的留言板，请友善地发言。</span><br></div><div id="valine-container"></div><script>Yun.utils.getScript("https://cdn.jsdelivr.net/npm/valine@latest/dist/Valine.min.js", () => {
  const valineConfig = {"enable":true,"appId":"O3v2IWIbQY4NT5SuPUNEWOSt-MdYXbMMI","appKey":"bsHhi7jpWfTk1P3dkHeHjBTz","placeholder":"建议设置回复时使用的昵称哦","avatar":null,"meta":["nick"],"pageSize":10,"visitor":false,"highlight":true,"recordIP":false,"enableQQ":true,"el":"#valine-container","lang":"zh-cn"}
  valineConfig.path = "/2021/05/13/%E6%B4%97%E7%89%8C%E7%AE%97%E6%B3%95/"
  new Valine(valineConfig)
}, window.Valine);</script></div></main><footer class="sidebar-translate" id="footer"><div class="copyright"><span>&copy; 2021 </span><span class="with-love" id="animate"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-cloud-line"></use></svg></span><span class="author"> Shinya</span></div><div class="powered"><span>由 <a href="https://hexo.io" target="_blank" rel="noopener">Hexo</a> 驱动 v5.4.0</span><span class="footer-separator">|</span><span>主题 - <a rel="noopener" href="https://github.com/YunYouJun/hexo-theme-yun" target="_blank"><span>Yun</span></a> v1.6.1</span></div><div class="live_time"><span>大图书馆已经观察并记录这个世界</span><span id="display_live_time"></span><span class="moe-text">(●'◡'●)</span><script>function blog_live_time() {
  setTimeout(blog_live_time, 1000);
  const start = new Date('2021-03-23T17:10:02');
  const now = new Date();
  const timeDiff = (now.getTime() - start.getTime());
  const msPerMinute = 60 * 1000;
  const msPerHour = 60 * msPerMinute;
  const msPerDay = 24 * msPerHour;
  const passDay = Math.floor(timeDiff / msPerDay);
  const passHour = Math.floor((timeDiff % msPerDay) / 60 / 60 / 1000);
  const passMinute = Math.floor((timeDiff % msPerHour) / 60 / 1000);
  const passSecond = Math.floor((timeDiff % msPerMinute) / 1000);
  display_live_time.innerHTML = " " + passDay + " 天 " + passHour + " 小时 " + passMinute + " 分 " + passSecond + " 秒";
}
blog_live_time();
</script></div></footer><a class="hty-icon-button" id="back-to-top" aria-label="back-to-top" href="#"><svg class="icon" aria-hidden="true"><use xlink:href="#icon-arrow-up-s-line"></use></svg><svg class="progress-circle-container" viewBox="0 0 100 100"><circle class="progress-circle" id="progressCircle" cx="50" cy="50" r="48" fill="none" stroke="#0078E7" stroke-width="2" stroke-linecap="round"></circle></svg></a></div></body></html>